package com.leetcode.studyplan.algorithm.basis;

/**
 * 重点在于从何处对二维矩阵进行遍历，
 *  在有序数组中，二分数组的思想就是 中间的数 大于 左边的数，大于右边的数。所以关键点找能连续成为 中间的数
 *  那么 从左下角数的开始，即可。右边为大于它的数，上面为小于它的数
 */
public class L_74_SearchA2DMatrix {

    public static void main(String[] args) {
        int[][] nums = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        int target = 13;
        L_74_SearchA2DMatrix matrix = new L_74_SearchA2DMatrix();
        System.out.println(matrix.searchMatrix(nums, target));
    }

    public boolean searchMatrix(int[][] matrix, int target) {

        int row = matrix.length - 1;
        int col = 0;

        while (row >= 0 && col <= matrix[0].length - 1) {

            if (matrix[row][col] == target) {
                return true;
            }
            if (matrix[row][col] > target) {
                row--;
            } else {
                col++;
            }
        }

        return false;
    }
}
